package com.hancher.gamelife2.noisedetect;

/**
 * 描述 :  <br/>
 * 时间 : 2024/5/23 18:07 <br/>
 * 作者 : Hancher ytu_shaoweijie@163.com
 */
public class FFT {
    /**
     * input是输入的数据（数据类型必须是Complex类型，需要调用Complex类里的Complex（）方法把数据转换为复数），N是数据的长度（数据长度必须是2的幂）返回值是复数数组
     * 调用Complex（）方法将数据转换为复数举例：
     *
     *      double[] data= {-0.35668879080953375, -0.6118094913035987, 0.8534269560320435, -0.6699697478438837, 0.35425500561437717,
     *                 0.8910250650549392, -0.025718699518642918, 0.07649691490732002};
     * 		N=8;
     * 		//傅里叶变换计算
     * 		Complex[] input = new Complex[N];//声明复数数组
     *   	//将实数数据转换为复数数据
     * 		for (int i = 0; i <= N-1; i++) {
     * 			input[i] = new Complex(data[i], 0);
     *        }
     *
     * 	    //傅里叶变换
     * 		input = FFT.getFFT(input, N);
     *  	//计算傅里叶变换得到的复数数组的模值
     * 		x=Complex.toModArray(input);
     * 		for(int i=0;i<=N-1;i++) {
     * 		    //的模值数组除以N再乘以2
     * 		    x1[i]=x[i]/N*2;
     *      }
     *
     * @param input
     * @param N
     * @return
     */
    public static Complex[] getFFT(Complex[] input, int N) {
        if ((N / 2) % 2 == 0) {
            Complex[] even = new Complex[N / 2];// 偶数
            Complex[] odd = new Complex[N / 2];// 奇数
            for (int i = 0; i < N / 2; i++) {
                even[i] = input[2 * i];
                odd[i] = input[2 * i + 1];
            }
            even = getFFT(even, N / 2);
            odd = getFFT(odd, N / 2);
            for (int i = 0; i < N / 2; i++) {
                Complex[] res = Complex.butterfly(even[i], odd[i], Complex.GetW(i, N));
                input[i] = res[0];
                input[i + N / 2] = res[1];
            }
            return input;
        } else {// 两点DFT,直接进行碟形运算
            Complex[] res = Complex.butterfly(input[0], input[1], Complex.GetW(0, N));
            return res;
        }
    }
}